package LiKo.CharacterString;

import java.util.*;

class Solution {
    public List<String> fizzBuzz(int n) {
        /*给你一个整数 n ，找出从 1 到 n 各个整数的 Fizz Buzz 表示，并用字符串数组 answer（下标从 1 开始）返回结果，其中：
answer[i] == "FizzBuzz" 如果 i 同时是 3 和 5 的倍数。
answer[i] == "Fizz" 如果 i 是 3 的倍数。
answer[i] == "Buzz" 如果 i 是 5 的倍数。
answer[i] == i （以字符串形式）如果上述条件全不满足。*/
        List<String> res = new LinkedList<>();
        for(int i =0 ;  i < n ; i++){
            int k = i+1;
            if(k % 3 == 0 && k % 5 == 0){
                res.add("FizzBuzz");
            }else if(k % 3 == 0){
                res.add("Fizz");
            }else if( k % 5 == 0){
                res.add("Buzz");
            }else{
                res.add(String.valueOf(k));
            }
        }
        return res;
    }
    public String[] findRelativeRanks(int[] score) {
          /*给你一个长度为 n 的整数数组 score ，其中 score[i] 是第 i 位运动员在比赛中的得分。所有得分都 互不相同 。
        运动员将根据得分 决定名次 ，其中名次第 1 的运动员得分最高，名次第 2 的运动员得分第 2 高，依此类推。运动员的名次决定了他们的获奖情况：
        名次第 1 的运动员获金牌 "Gold Medal" 。
        名次第 2 的运动员获银牌 "Silver Medal" 。
        名次第 3 的运动员获铜牌 "Bronze Medal" 。
        从名次第 4 到第 n 的运动员，只能获得他们的名次编号（即，名次第 x 的运动员获得编号 "x"）。
        使用长度为 n 的数组 answer 返回获奖，其中 answer[i] 是第 i 位运动员的获奖情况。*/
        int n = score.length;
        String[] desc = {"Gold Medal", "Silver Medal", "Bronze Medal"};
        int[][] arr = new int[n][2];

        for (int i = 0; i < n; ++i) {
            arr[i][0] = score[i];
            arr[i][1] = i;
        }
        Arrays.sort(arr, (a, b) -> b[0] - a[0]);
        String[] ans = new String[n];
        for (int i = 0; i < n; ++i) {
            if (i >= 3) {
                ans[arr[i][1]] = Integer.toString(i + 1);
            } else {
                ans[arr[i][1]] = desc[i];
            }
        }
        return ans;
    }
    public int findMinDifference(List<String> timePoints) {
        Collections.sort(timePoints);
        int ans = Integer.MAX_VALUE;
        int t0Minutes = getMinutes(timePoints.get(0));
        int preMinutes = t0Minutes;
        for (int i = 1; i < timePoints.size(); ++i) {
            int minutes = getMinutes(timePoints.get(i));
            ans = Math.min(ans, minutes - preMinutes); // 相邻时间的时间差
            preMinutes = minutes;
        }
        ans = Math.min(ans, t0Minutes + 1440 - preMinutes); // 首尾时间的时间差
        return ans;
    }

    public int getMinutes(String t) {
        return ((t.charAt(0) - '0') * 10 + (t.charAt(1) - '0')) * 60 + (t.charAt(3) - '0') * 10 + (t.charAt(4) - '0');
    }
    public boolean isSubsequence(String s, String t) {
        /*给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
        字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。
        （例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
        进阶：
        如果有大量输入的 S，称作 S1, S2, ... , Sk 其中 k >= 10亿，
        你需要依次检查它们是否为 T 的子序列。在这种情况下，你会怎样改变代码？*/
        // 判断是否存在这个字符 , 第二判断字符顺序是不是在了
        int fast =0 ,slow = 0;//快慢指针
        while (fast < t.length()){
            if (slow < s.length() &&s.charAt(slow) == t.charAt(fast)){
                slow++;
            }
            fast++;
        }
        return slow == s.length();

    }
    public String findLongestWord(String s, List<String> dictionary) {
        int fast=0,slow=0;
        int len =0,k =0;
        for (int i = 0; i < dictionary.size(); i++) {
            if (isSubsequence(dictionary.get(i),s)){

                if (dictionary.get(i).length() > len){
                    len = dictionary.get(i).length();
                    k = i;
                }else if (dictionary.get(i).length() == len){
                   if (dictionary.get(i).compareTo(dictionary.get(k)) <  0){
                       k = i;
                   }
                }

            }
        }
        if (len == 0)return "";
        return dictionary.get(k);
    }
    public int findLUSlength(String a, String b) {
        /*给你两个字符串 a 和 b，请返回 这两个字符串中 最长的特殊序列  的长度。如果不存在，则返回 -1 。
            「最长特殊序列」 定义如下：该序列为 某字符串独有的最长子序列（即不能是其他字符串的子序列） 。
            字符串 s 的子序列是在从 s 中删除任意数量的字符后可以获得的字符串。
            例如，"abc" 是 "aebdc" 的子序列，因为删除 "aebdc" 中斜体加粗的字符可以得到 "abc" 。
            "aebdc" 的子序列还包括 "aebdc" 、 "aeb" 和 "" (空字符串)。*/

        if(a.equals(b))
            return -1;
        return a.length() > b.length() ? a.length() : b.length();
    }
//    public int findLUSlength(String[] strs) {
//       PriorityQueue<String> priorityQueue = new PriorityQueue<>(new Comparator<String>() {
//           @Override
//           public int compare(String o1, String o2) {
//               return o1.length()-o2.length();
//           }
//       });
//        for (int i = 0; i < strs.length; i++) {
//            if (i < 2){
//                priorityQueue.add(strs[i]);
//            }else {
//                if (strs[i].length() > priorityQueue.peek().length()){
//                    priorityQueue.poll();
//                    priorityQueue.offer(strs[i]);
//                }else if ()
//            }
//        }
//        String s1 = priorityQueue.poll();
//        String s2 = priorityQueue.poll();
//        if (s2.equals(s1))return -1;
//        return s2.length()>s1.length()?s2.length():s1.length();
//    }

    public int[] plusOne(int[] digits) {
        /*给数组的末位加1*/

        for (int i = digits.length - 1; i >= 0; i--) {
            if (digits[i] == 9) {
                digits[i] = 0;
            } else {
                digits[i] += 1;
                return digits;
            }

        }
        //如果所有位都是进位，则长度+1
        digits= new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }

    public String addBinary(String a, String b) {
        /*给你两个二进制字符串 a 和 b ，以二进制字符串的形式返回它们的和。*/
        StringBuilder res = new StringBuilder(); // 返回结果
        int i = a.length() - 1; // 标记遍历到 a 的位置
        int j = b.length() - 1; // 标记遍历到 b 的位置
        int carry = 0; // 进位
        while (i >= 0 || j >= 0 || carry != 0) { // a 没遍历完，或 b 没遍历完，或进位不为 0
            int digitA = i >= 0 ? a.charAt(i) - '0' : 0; // 当前 a 的取值
            int digitB = j >= 0 ? b.charAt(j) - '0' : 0; // 当前 b 的取值
            int sum = digitA + digitB + carry; // 当前位置相加的结果
            carry = sum >= 2 ? 1 : 0; // 是否有进位
            sum = sum >= 2 ? sum - 2 : sum; // 去除进位后留下的数字
            res.append(sum); // 把去除进位后留下的数字拼接到结果中
            i --;  // 遍历到 a 的位置向左移动
            j --;  // 遍历到 b 的位置向左移动
        }
        return res.reverse().toString(); // 把结果反转并返回
    }




}